/**
 * @file binarytree.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-15
 * 
 * @copyright Copyright (c) 2021
 * 
 * 27.二叉树的镜像
 * 55.I.二叉树的深度 -- 最大深度
 * 68.II.二叉树的最近公共祖先
 * 07.重建二叉树 -- 根据前序+中序还原二叉树
 * 32.I.从上到下打印二叉树 -- 就是层序遍历
 * 32.II.从上到下打印二叉树II
 * 55.II.平衡二叉树
 * 28.对称二叉树 -- 类比相同的树
 * 26.树的子结构 -- 区别于另一棵树的子树
 * 37.序列化二叉树
 */

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
        : val(val), left(left), right(right) {}
};

class Solution
{
public:
#if 0
    // 27. 递归
    TreeNode* mirrorTree(TreeNode* root) {
        if (root == nullptr){
            return nullptr;
        }
        TreeNode *left = mirrorTree(root->left);
        TreeNode *right = mirrorTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};
    // 27. 栈
    TreeNode* mirrorTree(TreeNode* root) {
        stack<TreeNode *> stk;
        if (root){
            stk.push(root);
        }
        while (!stk.empty()){
            TreeNode *node = stk.top();         
            TreeNode *right = node->right;
            TreeNode *left = node->left;
            node->left = right;
            node->right = left;
            stk.pop();
            if (node->right){
                stk.push(node->right);
            }
            if (node->left){
                stk.push(node->left);
            }
        }
        return root;
    }
};
#endif
    // 27. 层序 镜像二叉树
    TreeNode *mirrorTree(TreeNode *root)
    {
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            while (n--) {
                TreeNode *node = q.front();
                TreeNode *right = node->right;
                TreeNode *left = node->left;
                node->left = right;
                node->right = left;
                q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
        }
        return root;
    }
    // 55.I 最大深度
    int maxDepth(TreeNode *root)
    {
        // 层序：++cnt
        // 递归：左右子树最大深度+1
        if (root == nullptr) {
            return 0;
        }
        return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
    // 68.II.最近公共祖先
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        // 后序遍历找到等于pq的节点
        if (root == nullptr || root == p || root == q) {
            return root;
        }
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left && right) { // p,q分散在左右子树
            return root;
        }
        if (left == nullptr) {
            return right;
        }
        return left;
    }

    // 07. 根据前序和中序还原二叉树
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        // 根据前序+中序构建二叉树
        if (preorder.empty()) {
            return nullptr;
        }
        int n = preorder.size();
        // 构建中序的map，帮助定位root位置
        for (int i = 0; i < n; ++i) {
            mp[inorder[i]] = i;
        }
        return build(preorder, inorder, 0, n - 1, 0, n - 1);
    }

private:
    unordered_map<int, int> mp;
    // 左闭右闭区间[i, j]
    TreeNode *build(vector<int> &preorder, vector<int> &inorder, int pi, int pj, int ii, int ij)
    {
        if (pi > pj) {
            return nullptr;
        }
        int inorderIndexOfRoot = mp[preorder[pi]]; // inorder中root的index
        TreeNode *root = new TreeNode(preorder[pi]);
        // 左子树的前序+中序
        int leftSize = inorderIndexOfRoot - ii; // 左子树size
        root->left = build(preorder, inorder, pi + 1, pi + leftSize, ii, inorderIndexOfRoot - 1);
        // 右子树的前序+中序
        root->right = build(preorder, inorder, pi + leftSize + 1, pj, inorderIndexOfRoot + 1, ij);
        return root;
    }

public:
    // 32.I.
    vector<int> levelOrder(TreeNode *root)
    {
        // 这尼玛不就是层序遍历么
        vector<int> res;
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            while (n--) {
                TreeNode *node = q.front();
                res.push_back(node->val);
                q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
        }
        return res;
    }
    // 32.II.
    vector<vector<int>> levelOrderII(TreeNode *root)
    {
        // 。。。
        vector<vector<int>> res;
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            vector<int> layer;
            while (n--) {
                TreeNode *node = q.front();
                layer.push_back(node->val);
                q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            res.emplace_back(layer);
        }
        return res;
    }
    // 32.III.
    vector<vector<int>> levelOrderIII(TreeNode *root)
    {
        vector<vector<int>> res;
        int cnt = 0;
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            vector<int> layer;
            ++cnt;
            while (n--) {
                TreeNode *node = q.front();
                layer.push_back(node->val);
                q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            if (cnt % 2 == 0) {
                std::reverse(layer.begin(), layer.end());
            }
            res.emplace_back(layer);
        }
        return res;
    }

    // 55.II.
    bool isBalanced(TreeNode *root)
    {
        // 左右子树高度之差
        return balanceTreeHeight(root) == -1 ? false : true;
    }

private:
    int balanceTreeHeight(TreeNode *root)
    {
        // 返回树高，若非平衡树返回-1
        if (root == nullptr) {
            return 0;
        }
        int leftHeight = balanceTreeHeight(root->left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = balanceTreeHeight(root->right);
        if (rightHeight == -1) {
            return -1;
        }
        if (::abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return std::max(leftHeight, rightHeight) + 1;
        }
    }

public:
    // 28.
    bool isSymmetric(TreeNode *root)
    {
        if (root == nullptr) {
            return true;
        }
        return isSymmetric(root->left, root->right);
    }

private:
    bool isSymmetric(TreeNode *left, TreeNode *right)
    {
        if (left == nullptr && right == nullptr) {
            return true;
        } else if (left == nullptr || right == nullptr || left->val != right->val) {
            return false;
        } else {
            return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
        }
    }

public:
    // 26.树的子结构 -- 区别于另一棵树的子树
    bool isSubStructure(TreeNode *A, TreeNode *B)
    {
        if (A == nullptr || B == nullptr) {
            return false;
        }
        return hasSub(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }

private:
    bool hasSub(TreeNode *t1, TreeNode *t2)
    {
        if (t2 == nullptr) {
            return true;
        } else if (t1 == nullptr || t1->val != t2->val) {
            return false;
        } else {
            return hasSub(t1->left, t2->left) && hasSub(t1->right, t2->right);
        }
    }
};

// 37.序列化二叉树与反序列化
class Codec
{
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode *root)
    {
        // 序列化的协议自己设定
        // root = [1,2,3,null,null,14,15]
        // res = "1,2,3,#,#,14,15,#,#,#,#"
        string res;
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            while (n--) {
                TreeNode *node = q.front();
                q.pop();
                if (node == nullptr) {
                    res.push_back(',');
                    res.push_back('#');
                } else if (res.empty()) {
                    res.append(to_string(node->val));
                } else {
                    res.push_back(',');
                    res.append(to_string(node->val));
                }
                if (node) {
                    q.push(node->left);
                    q.push(node->right);
                }
            }
        }
        // cout << res << endl;
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data)
    {
        if (data.empty()) {
            return nullptr;
        }
        // c++ string没有split，实现一个类似split
        // 若 data: "1,2,3,#,#,14,15,#,#,#,#"
        // 则 serial: "1","2","#",...,"15",..."#"
        vector<string> serial(1, "");
        for (int i = 0, p = 0; i < data.size(); ++i) {
            if (data[i] == ',') {
                serial.emplace_back(""); // 揉一个空串
                ++p;
            } else {
                serial[p].push_back(data[i]); // 往当前字符串里添加字符
            }
        }
        TreeNode *root = new TreeNode(stoi(serial[0]));
        queue<TreeNode *> q;
        q.push(root);
        int i = 0;
        while (i < serial.size() - 1) {
            TreeNode *node = q.front();
            q.pop();
            // 每个非空节点后面必有俩孩子(孩子可能是空节点)
            string left = serial[i + 1];
            string right = serial[i + 2];
            if (left != "#") {
                node->left = new TreeNode(stoi(left));
                q.push(node->left);
            }
            if (right != "#") {
                node->right = new TreeNode(stoi(right));
                q.push(node->right);
            }
            i += 2;
        }
        return root;
    }
};

template <class T>
void print(const T &t)
{
    typename T::const_iterator it = t.cbegin();
    for (; it != t.cend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

void test() // s.split(',')
{
    string data = "1,2,3,#,#,14,15,#,#,#,#";
    vector<string> nums(1, "");
    for (int i = 0, p = 0; i < data.size(); ++i) {
        if (data[i] == ',') {
            nums.emplace_back("");
            ++p;
        } else {
            nums[p].push_back(data[i]);
        }
    }
    cout << nums.size() << endl;
    cout << nums[3] << endl;
    cout << nums[6] << endl;
    print(nums);
}

int main()
{
    test();
    return 0;
}